package leetcode;

public class lc_494 {
    static int s = 0;
    public static void main(String[] args) {
        System.out.println(findTargetSumWays2(new int[]{1,1,1,1,1}, 3));
    }
    //回溯
    public static int findTargetSumWays(int[] nums, int target) {
        dfs(nums,target,0,0);
        return s;
    }
    public static void dfs(int[] nums, int target, int sum, int index){
        if(sum == target && index == nums.length){
            s++;
            return;
        }
        if(index < nums.length) {
            dfs(nums, target, sum + nums[index], index + 1);
            dfs(nums, target, sum - nums[index], index + 1);
        }
    }
    //动态规划
    public static int findTargetSumWays1(int[] nums, int target) {
        /**
         * 假设正数和x，负数和y
         * s为 nums的和
         * x + y = s
         * y = s - x
         * target = x - (s - x)
         * x = (target + s) / 2
         * 转换为01背包问题 装满x的组合
         * 求组合类问题的公式，都是类似这种：
         * dp[j] += dp[j - nums[i]]
         */

        int s = 0;
        for (int i = 0; i < nums.length; i++) {
            s += nums[i];
        }
        int x = (target + s) / 2;
        if(Math.abs(target) > s)
            return 0;
        if((target + s) % 2 == 1)
            return 0;
        int[] dp = new int[x + 1];
        dp[0] = 1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = x; j >= nums[i] ; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[x];
    }

    //二维dp
    public static int findTargetSumWays2(int[] nums, int target) {
        /**
         * 假设正数和x，负数和y
         * s为 nums的和
         * x + y = s
         * y = s - x
         * target = x - (s - x)
         * x = (target + s) / 2
         * 转换为01背包问题 装满x的组合
         */

        int s = 0;
        int n = nums.length;
        for (int i = 0; i < n; i++) {
            s += nums[i];
        }
        int x = (target + s) / 2;
        if(Math.abs(target) > s)
            return 0;
        if((target + s) % 2 == 1)
            return 0;
        int[][] dp = new int[n + 1][x + 1];
        dp[0][0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j <= x; j++) {
                if(j >= nums[i - 1]){
                    dp[i][j] = dp[i - 1][j - nums[i - 1]] + dp[i - 1][j];
                }
                else{
                    dp[i][j] = dp[i - 1][j];
                }
            }
        }
        for (int i = 0; i <= n; i++) {
            for (int j = 0; j <= x; j++) {
                System.out.print(String.format("%2d", dp[i][j]) + " ");
            }
            System.out.println();
        }
        return dp[n][x];
    }
}